/*------------------------------------------------------------------------
 *
 * geqo_eval.c
 *	  评估查询树的例程
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * src/backend/optimizer/geqo/geqo_eval.c
 *
 *-------------------------------------------------------------------------
 */

/* 贡献者：
   =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
   *  Martin Utesch				 * 自动控制研究所		   *
   =							 = 矿业与技术大学 =
   *  utesch@aut.tu-freiberg.de  * 德国弗赖贝格				   *
   =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
 */

#include "postgres.h"

#include <float.h>
#include <limits.h>
#include <math.h>

#include "optimizer/geqo.h"
#include "optimizer/joininfo.h"
#include "optimizer/pathnode.h"
#include "optimizer/paths.h"
#include "utils/memutils.h"


/* gimme_tree 中已经连接关系的 "团" */
typedef struct
{
	RelOptInfo *joinrel;		/* joinrel 用于关系集 */
	int			size;			/* 团内输入关系的数量 */
} Clump;

static List *fc_merge_clump(PlannerInfo *fc_root, List *fc_clumps, Clump *fc_new_clump,
						 int fc_num_gene, bool fc_force);
static bool fc_desirable_join(PlannerInfo *fc_root,
						   RelOptInfo *fc_outer_rel, RelOptInfo *fc_inner_rel);


/*
 * geqo_eval
 *
 * 返回作为种群个体的查询树的成本。
 *
 * 如果无法从提议的巡回中提取合法的连接顺序，
 * 则返回 DBL_MAX。
 */
Cost
geqo_eval(PlannerInfo *fc_root, Gene *fc_tour, int fc_num_gene)
{
	MemoryContext fc_mycontext;
	MemoryContext fc_oldcxt;
	RelOptInfo *fc_joinrel;
	Cost		fc_fitness;
	int			fc_savelength;
	struct HTAB *fc_savehash;

	/*
	 * 创建一个私有内存上下文，将保存
	 * 在 gimme_tree() 中分配的所有临时存储
	 *
	 * 由于 geqo_eval() 将被多次调用，我们不能允许
	 * 在语句结束之前让所有这些内存都未被回收。注意，我们将
	 * 临时上下文设置为计划者正常上下文的子项，因此即使
	 * 我们通过 ereport(ERROR) 中止，它也会被释放。
	 */
	fc_mycontext = AllocSetContextCreate(CurrentMemoryContext,
									  "GEQO",
									  ALLOCSET_DEFAULT_SIZES);
	fc_oldcxt = MemoryContextSwitchTo(fc_mycontext);

	/*
	 * gimme_tree 将向 root->join_rel_list 添加条目，该列表可能已经
	 * 包含一些条目。新添加的条目将通过下面的 MemoryContextDelete
	 * 来回收，因此我们必须确保在退出之前列表恢复到原来的状态。
	 * 我们可以通过将列表截断为其原始长度来做到这一点。注意，这假设
	 * 所有添加的条目都是附加在最后的！
	 *
	 * 我们还必须注意不要搞乱外部 join_rel_hash（如果存在的话）。
	 * 我们可以通过暂时将链接设置为 NULL 来做到这一点。
	 * （如果我们处理足够的 join rels，这很可能是这样，则会构建新的
	 * 哈希表并在本地使用。）
	 *
	 * join_rel_level[] 不应该在使用中，因此只需断言它没有被使用。
	 */
	fc_savelength = list_length(fc_root->join_rel_list);
	fc_savehash = fc_root->join_rel_hash;
	Assert(fc_root->join_rel_level == NULL);

	fc_root->join_rel_hash = NULL;

	/* 为给定的关系组合构建最佳路径 */
	fc_joinrel = gimme_tree(fc_root, fc_tour, fc_num_gene);

	/*
	 * 计算适应度，如果找到有效的连接
	 *
	 * XXX geqo 当前不支持部分结果检索的优化，
	 * 也没有考虑参数化路径的可能使用 --- 如何解决？
	 */
	if (fc_joinrel)
	{
		Path	   *fc_best_path = fc_joinrel->cheapest_total_path;

		fc_fitness = fc_best_path->total_cost;
	}
	else
		fc_fitness = DBL_MAX;

	/*
	 * 将 join_rel_list 恢复到之前的状态，如果有的话，放回原始
	 * 哈希表。
	 */
	fc_root->join_rel_list = list_truncate(fc_root->join_rel_list,
										fc_savelength);
	fc_root->join_rel_hash = fc_savehash;

	/* 释放 gimme_tree 中获取的所有内存 */
	MemoryContextSwitchTo(fc_oldcxt);
	MemoryContextDelete(fc_mycontext);

	return fc_fitness;
}

/*
 * gimme_tree
 *	  为按照指定顺序构建的连接树形成规划估算。
 *
 *	 'tour' 是提议的连接顺序，长度为 'num_gene'
 *
 * 返回一个新的连接关系，其最便宜的路径是该连接顺序的最佳计划。
 * 注意：如果连接顺序无效且无法将其修改为有效顺序，将返回 NULL。
 *
 * 该例程的原始实现总是按照指定顺序连接，因此只能构建左侧计划
 * （以及右侧和混合计划，作为 make_join_rel() 对称性的副产品）。
 * 它从来不能生成“灌木丛”计划。这存在几个重大问题，
 * 其中最严重的是在涉及连接顺序限制的情况下，唯一有效的计划是灌木丛计划。
 *
 * 当前的实现将给定的游程作为指导，但
 * 推迟那些由于某些启发式规则被认为非法或不合适的连接。
 * 这允许在需要时生成正确的灌木丛计划，
 * 作为一个良好的副作用，似乎会显著改善生成计划的质量。
 * 然而请注意，由于这只是一个启发式规则，它在某些情况下仍可能失败。
 * （特别是，我们可能将实际上由于 LATERAL 限制而必需
 * 不被连接的关系聚集在一起；由于没有解除聚集的规定，这必然导致失败。）
 */
RelOptInfo * gimme_tree(PlannerInfo *fc_root, Gene *fc_tour, int fc_num_gene)
{
	GeqoPrivateData *fc_private = (GeqoPrivateData *) fc_root->join_search_private;
	List	   *fc_clumps;
	int			fc_rel_count;

	/*
	 * 有时，由于启发式或实际语义限制，某个关系无法与其他关系连接。
	 * 我们维护一个成功连接关系的“聚类”列表，
	 * 较大的聚类位于前面。来自游程的每个新关系都被添加到它可以连接的第一个聚类；
	 * 如果没有，则它成为一个新的聚类。当我们
	 * 扩大现有聚类时，我们检查它是否可以与其他聚类合并。
	 * 所有游程扫描完后，我们会忘记启发式规则，
	 * 尝试强制连接任何剩余的聚类。如果我们无法将所有聚类合并为一个，则失败。
	 */
	fc_clumps = NIL;

	for (fc_rel_count = 0; fc_rel_count < fc_num_gene; fc_rel_count++)
	{
		int			fc_cur_rel_index;
		RelOptInfo *fc_cur_rel;
		Clump	   *fc_cur_clump;

		/* 获取下一个输入关系 */
		fc_cur_rel_index = (int) fc_tour[fc_rel_count];
		fc_cur_rel = (RelOptInfo *) list_nth(fc_private->initial_rels,
										  fc_cur_rel_index - 1);

		/* 将其转化为单关系聚类 */
		fc_cur_clump = (Clump *) palloc(sizeof(Clump));
		fc_cur_clump->joinrel = fc_cur_rel;
		fc_cur_clump->size = 1;

		/* 将其合并到聚类列表中，仅使用期望的连接 */
		fc_clumps = fc_merge_clump(fc_root, fc_clumps, fc_cur_clump, fc_num_gene, false);
	}

	if (list_length(fc_clumps) > 1)
	{
		/* 按某种合法顺序强制连接剩余的聚类 */
		List	   *fc_fclumps;
		ListCell   *fc_lc;

		fc_fclumps = NIL;
		foreach(fc_lc, fc_clumps)
		{
			Clump	   *fc_clump = (Clump *) lfirst(fc_lc);

			fc_fclumps = fc_merge_clump(fc_root, fc_fclumps, fc_clump, fc_num_gene, true);
		}
		fc_clumps = fc_fclumps;
	}

	/* 我们是否成功形成了一个单一的连接关系？ */
	if (list_length(fc_clumps) != 1)
		return NULL;

	return ((Clump *) linitial(fc_clumps))->joinrel;
}

/*
 * 将一个“聚类”合并到 gimme_tree 的现有聚类列表中。
 *
 * 我们尝试将聚类合并到某个现有聚类中，如果成功则重复此过程。
 * 当无法再合并时，将聚类插入列表中，
 * 保持列表的顺序规则（即，较大的聚类在前）。
 *
 * 如果 force 为 true，在任何合法的连接处合并，
 * 即使这导致执行笛卡尔连接。
 * 当 force 为 false 时，仅执行“期望”的连接。
 */
static List * fc_merge_clump(PlannerInfo *fc_root, List *fc_clumps, Clump *fc_new_clump, int fc_num_gene,
			bool fc_force)
{
	ListCell   *fc_lc;
	int			fc_pos;

	/* 寻找可以连接到 new_clump 的聚类 */
	foreach(fc_lc, fc_clumps)
	{
		Clump	   *fc_old_clump = (Clump *) lfirst(fc_lc);

		if (fc_force ||
			fc_desirable_join(fc_root, fc_old_clump->joinrel, fc_new_clump->joinrel))
		{
			RelOptInfo *fc_joinrel;

			/*
			 * 构建一个 RelOptInfo，表示这两个输入关系的连接。
			 * 注意，我们预计 joinrel 尚不存在于 root->join_rel_list 中，
			 * 因此为其构建的路径将仅包括我们想要的路径。
			 */
			fc_joinrel = make_join_rel(fc_root,
									fc_old_clump->joinrel,
									fc_new_clump->joinrel);

			/* 如果连接顺序无效，则继续搜索 */
			if (fc_joinrel)
			{
				/* 为分区连接创建路径。 */
				generate_partitionwise_join_paths(fc_root, fc_joinrel);

				/*
				 * 除了最上面的扫描/连接关系之外，
				 * 考虑收集部分路径。
				 * 一旦我们知道最终的目标列表（见
				 * grouping_planner），我们将对最上面的扫描/连接
				 * 关系执行相同操作。
				 */
				if (!bms_equal(fc_joinrel->relids, fc_root->all_baserels))
					generate_useful_gather_paths(fc_root, fc_joinrel, false);

				/* 查找并保存此连接关系的最便宜路径 */
				set_cheapest(fc_joinrel);

				/* 吸收新聚类到旧的中 */
				fc_old_clump->joinrel = fc_joinrel;
				fc_old_clump->size += fc_new_clump->size;
				pfree(fc_new_clump);

				/* 从列表中移除 old_clump */
				fc_clumps = foreach_delete_current(fc_clumps, fc_lc);

				/*
				 * 递归尝试将扩大的 old_clump 与
				 * 其他聚类合并。当无法进一步合并时，
				 * 我们将重新插入到列表中。
				 */
				return fc_merge_clump(fc_root, fc_clumps, fc_old_clump, fc_num_gene, fc_force);
			}
		}
	}

	/*
	 * 无法合并，因此按适当顺序作为独立聚类添加 new_clump，
	 * 按大小排序。对于大小为 1 的常见情况，
	 * 我们可以快速处理 --- 它应该总是放在最后。
	 */
	if (fc_clumps == NIL || fc_new_clump->size == 1)
		return lappend(fc_clumps, fc_new_clump);

	/* 否则寻找插入位置 */
	for (fc_pos = 0; fc_pos < list_length(fc_clumps); fc_pos++)
	{
		Clump	   *fc_old_clump = (Clump *) list_nth(fc_clumps, fc_pos);

		if (fc_new_clump->size > fc_old_clump->size)
			break;				/* new_clump 应位于 old_clump 之前 */
	}
	fc_clumps = list_insert_nth(fc_clumps, fc_pos, fc_new_clump);

	return fc_clumps;
}

/*
 * gimme_tree 的启发式：我们想要连接这两个关系吗？
 */
static bool fc_desirable_join(PlannerInfo *fc_root,
			   RelOptInfo *fc_outer_rel, RelOptInfo *fc_inner_rel)
{
	/*
	 * 如果有适用的连接条件，或者存在强制这些关系连接的连接顺序限制。
	 */
	if (have_relevant_joinclause(fc_root, fc_outer_rel, fc_inner_rel) ||
		have_join_order_restriction(fc_root, fc_outer_rel, fc_inner_rel))
		return true;

	/* 否则将连接推迟到稍后。 */
	return false;
}
